package TripleTable;
import ArrList.ArrList;
import SeqList.SeqList;
import Stack.Stack;

public class TripleTable<T> implements ITripleTable<T>{
    int len, size;
    public SeqList data;
    int[][] compromise;//实在没有办法了……
    int count;//记录二维数组中的行数

    public TripleTable(int size){
        data = new SeqList(size);
        for(int i = 0;i < size;i++){
            data.insert(i,new ThreeTuple());
        }
        this.size = size - 1;
        this.len = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.len == 0;
    }

    @Override
    public int getWeight(int row, int col) {
        for(int i = 0;i <= this.len;i++){
            if(this.data.getRow(i) == row && this.data.getCol(i) == col){
                return this.data.getWeight(i);
            }
        }
        return -1;
    }

    @Override
    public void set(int row, int col, int weight) {//可以用insert()方法替代
        for(int i = 0;i <= this.len;i++){
            if(this.data.getRow(i) == row && this.data.getCol(i) == col){
                this.data.setWeight(i, weight);
            }
            if(this.data.getRow(i) == col && this.data.getCol(i) == row){
                this.data.setWeight(i, weight);
            }
        }
    }

    @Override
    public int length() {//求景点个数
        return this.len;
    }

    @Override
    public void insert(int row, int col, int weight) {
        int flag = 0;
        for(int i = 0;i <= this.len;i++){//假如增加的路径为已有路径
            if(this.data.getRow(i) == row && this.data.getCol(i) == col){
                this.data.setWeight(i, weight);
                flag = 1;
            }
            if(this.data.getRow(i) == col && this.data.getCol(i) == row){
                this.data.setWeight(i, weight);
                flag = 1;
            }
        }
        if (flag == 1){
            return;
        }
        if (this.len == this.size){//满串扩容
            SeqList temp = this.data;
            this.data = new SeqList(size + 1);
            for(int i = 0;i < size; i++){
                this.data.set(i, temp.get(i));
            }
            this.size++;
        }
        data.setRow(this.len, row);
        data.setCol(this.len, col);
        data.setWeight(this.len, weight);
        this.len++;
    }

    @Override
    public void remove(int row, int col) {
        int flag = 0;
        for(int i = 0;i <= this.len;i++){
            if(this.data.getRow(i) == row && this.data.getCol(i) == col){
                for(int j = i; j < this.len - 1; j++){//把i后的数据元素依次前移
                    this.data.set(i, this.data.get(j));
                }
                this.len--;
                flag = 1;
            }
            if(this.data.getRow(i) == col && this.data.getCol(i) == row){
                for(int j = i; j < this.len - 1; j++){//同上
                    this.data.set(i, this.data.get(j));
                }
                this.len--;
            }
        }
        if(flag == 0){
            System.out.println("it's out of index.");
        }
    }

    @Override
    public void removeAll() {
        this.len = 0;
    }

    @Override
    public SeqList getData() {
        SeqList data = this.data;
        return data;
    }

    @Override
    public Object[] searchNear(int id){//查找与目标景点相邻的景点
        int j = 0;
        ArrList near = new ArrList(this.len);
        for(int i = 0;i <= this.len;i++){
            if (this.data.getRow(i) == id){
                near.lengthen(this.data.getCol(i));
                j++;
            }
        }
        /*
        for(int i = 0;i <= this.len;i++){
            if (this.data.getCol(i) == id){
                near.lengthen(this.data.getRow(i));
                j++;
            }
        }
        for(int i = 0;i <= j;i++){
            for (int k = i; k < j; k++) {
                if (near.get(i) == near.get(k)){
                    near.remove(k);
                }
            }
        }
         */
        //由于将三元组表的内存扩大了一倍，现无需此代码
        return near.getElements();
    }

    @Override
    public int[][] searchAll(int id1, int id2) {//查询两景点间所有路径
        Stack path = new Stack(this.len);
        ArrList arr = new ArrList(this.len);
        initialize();
        path.push(id1);
        search( id1, path, arr, 0, id2);
        return this.compromise;
    }

    public void search( int from, Stack path, ArrList arr ,int curLen, int end){
        int flag = 0;
        for (int i = 0; i < this.len; i++) {
            if (this.data.getRow(i) == (int) from){//判断该结点是否有通往未访问的结点的路径
                if (this.data.getCol(i) == end){//判断路径是否抵达终点
                    for (int j = 0; j < curLen; j++) {//储存路径
                        this.compromise[this.count][j] = (int)arr.get(j);
                        this.count++;
                    }
                    path.popTop();
                    curLen--;
                    return;
                }
                path.push(this.data.getCol(i));
                arr.set(curLen, this.data.getCol(i));
                curLen++;
                flag = 1;
                search((int)path.getTop(), path, arr, curLen, end);
            }
        }
        if (flag == 0){//判断查询是否有结果
            path.popTop();
            curLen--;
            return;
        }
    }

    public void initialize(){//初始化二维数组
        for (int i = 0; i < this.len; i++) {
            for (int j = 0; j < this.len; j++) {
                this.compromise[i][j] = 0;
            }
        }
        this.count = 0;
    }

    @Override
    public Object[] searchShortest(int id1, int id2) {//查询两景点间最短路径
        ArrList path = new ArrList(this.len);
        int shortestPath = 0;
        int leastWeight = -1;
        searchAll( id1, id2);
        for (int i = 0; i < count; i++) {//循环比较每一条路径的权重大小
            int j = 0;
            int totalWeight = 0;
            while(this.compromise[i][j] != 0){//求本路径的权重
                totalWeight += this.data.getWeight(this.compromise[i][j]);
                j++;
            }
            if (leastWeight == -1 || leastWeight > totalWeight){//比较现最短路径权重和本路径权重大小
                shortestPath = i;
                leastWeight = totalWeight;
            }
        }
        int k = 0;
        while (this.compromise[shortestPath][k] != 0){//将最短路径赋给path
            path.set( k, this.compromise[shortestPath][k]);
            k++;
        }
        return path.getElements();
    }
}
